Median & Order Statistic

Order Statistic( i 번째로 작은 값 )
을 구할 때, 정렬 후 값을 찾을 수 있다. 이는 O(n lgn)의 하한에 구애 받는다.
만일 정렬하지 않고 i 번째로 작은 값만 구할 경우, O(n) 선형 시간에 찾을 수 있다.
최솟값과 최댓값(Minimum and Maximum Value)
#include <iostream>
using namespace std;
struct twoint{
int first, second;
twoint(int _first, int _second): first(_first), second(_second){}
};
template <typename T>
T Minimum(T* arr, int size){
T min=arr[0];
for(int i=1; i<size; ++i){
if(min>arr[i]) min=arr[i];
}
return min;
}
template <typename T>
T Maximum(T* arr, int size){
T max=arr[0];
for(int i=1; i<size; ++i){
if(max<arr[i]) max=arr[i];
}
return max;
}
template <typename T>
twoint MinMax(T* arr, int size){
int min, max, crt_min, crt_max, start;
if(size%2==0){
if(arr[0]>arr[1]){
min=arr[1]; max=arr[0];
} else {
min=arr[0]; max=arr[1];
}
start=2;
} else {
min=arr[0]; max=arr[0];
start=1;
}
for(int i=start; i<size; i+=2){
if(arr[i]>arr[i+1]){
crt_min=arr[i+1]; crt_max=arr[i];
} else {
crt_min=arr[i]; crt_max=arr[i+1];
}
if(min>crt_min) min=crt_min;
if(max<crt_max) max=crt_max;
}
return twoint(min, max);
}
int main(void){
int arr[]={3, 4, 6, 7, 9, 11, 15};
int size=sizeof(arr)/sizeof(int);
cout<<"Minimum: "<<Minimum<int>(arr, size)<<'\n';
cout<<"Maximum: "<<Maximum<int>(arr, size)<<endl;
twoint result=MinMax(arr, size);
cout<<"Min: "<<result.first<<" Max: "<<result.second<<endl;
return 0;
}
순서 통계량 선택: Randomized Select
랜덤 퀵 정렬이 양쪽으로 분할했던 것과 달리 한쪽만 분할함
#include <random>
#include <iostream>
#define swap(i, j){int tmp=i; i=j; j=tmp;}
std::random_device rd;
std::mt19937 gen(rd());
using namespace std;
int Partition(int* arr, int p, int r){
int x=arr[r];
int i=p-1;
for(int j=p; j<r; ++j){
if(arr[j]<=x){
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i+1], arr[r]);
return i+1; // crt index
}
int Randomized_Partition(int* arr, int p, int r){
std::uniform_int_distribution<int> runif(p, r);
int i=runif(gen);
swap(arr[r], arr[i]);
return Partition(arr, p, r);
}
int Randomized_Select(int* arr, int p, int r, int i){
if(p==r) return arr[p];
int q=Randomized_Partition(arr, p, r);
if(i==q) return arr[q];
else if(i<q) return Randomized_Select(arr, p, q-1, i);
else return Randomized_Select(arr, q+1, r, i);
}
int main(void){
int arr[]={5, 3, 6, 2, 7, 9};
int size=sizeof(arr)/sizeof(int), result;
for(int i=0; i<size; ++i){
result=Randomized_Select(arr, 0, size-1, i);
cout<<"Result: "<<result<<endl;
}
return 0;
}